#ifndef SORT_QSORT_HPP
#define SORT_QSORT_HPP

#include "../common.hpp"

YFWZ100_NS_BEGIN

template <typename T>
void qsort(T arr[], int start, int end)
{
  if (start >= end - 1) return;

  T key = arr[start];
  int i = start, j = end - 1;
  while (i < j) {
    // arr[j] 比 key 大或相等
    while (i < j && arr[j] >= key) j --;
    swap(arr[i], arr[j]);
    // arr[i] 比 key 小或相等
    while (i < j && arr[i] <= key) i ++;
    swap(arr[j], arr[i]);
  }
  // 此时 i 和 j 是相等的，代表中间位置，即赋值为原来的 key
  arr[i] = key;
  qsort(arr, start, i);
  qsort(arr, i + 1, end);
}

template <typename PointerLike>
void qsort(PointerLike start, PointerLike end)
{
  if (start >= end - 1) return;

  auto key = *start;
  PointerLike i = start, j = end - 1;
  while (i < j) {
    while (i < j && *j >= key) j --;
    swap(*i, *j);

    while (i < j && *i <= key) i ++;
    swap(*j, *i);
  }
  *j = key;

  qsort(start, i);
  qsort(i + 1, end);
}

YFWZ100_NS_END

#endif//SORT_QSORT_HPP
